//20210808
/**
 * 解题思路：通过栈来解决(先进后匹配的规律)
 * 栈的最后一位与当前brackets的索引元素匹配则出栈，要是不匹配则进栈
 * 注意：
 * 预防当前brackets的索引元素有可能是undefined和stack[最后一位]为undefined
 * 1.找连续子串，因为当匹配就出栈，所以栈中的顶部永远都是无法匹配的最后一个元素位置，拿当前位置减它就可以得到子串的总长度
 * 计算最大长度公式：
 * cur=当前位置（i）-栈顶部最后的元素（就是匹配到的元素前一位）=i-stack[stack.length-1]
 * max(max,cur)
 * 
 * @param {string} s
 * @return {boolean}
 */
var longestValidParentheses = function(s) {
    let maxlength=0;
    // 因为字符串是从0开始的，所以要求它的长度= 元素尾部（length-1)-1=length,这个元素不会被删除也不应该被删除
    let stack=[-1];
    for(let i=0;i<s.length;i++){
        if(s[i]=="("){
            stack.push(i);
        }else{
            stack.pop();
            // 栈中是否有最后一位无法匹配到的元素
            if(stack.length){
                // 获取栈中最顶部的索引(上一个不匹配的元素位置)
                const topIndex=stack[stack.length-1]
                // 当前索引-栈中最顶部的索引(当前匹配的元素位置减去上一个不匹配的元素位置)
                const curMaxLen = i - topIndex; // 计算有效连续长度
                console.log(i,topIndex)
                // 获取最大值
                maxlength=Math.max(maxlength,curMaxLen);
            }else{
                // 确保栈中有一个最后无法被匹配的位置
               stack.push(i);
             }
        }
        console.log(stack,maxlength)
    }
    return maxlength;
};


// console.assert(longestValidParentheses("(()") === 2, "Test Case 1 Failed");
console.assert(longestValidParentheses(")()())") === 4, "Test Case 2 Failed");
// console.assert(longestValidParentheses("") === 0, "Test Case 3 Failed");
// console.assert(longestValidParentheses("()") === 2, "Test Case 4 Failed");
// console.assert(longestValidParentheses("()(()") === 2, "Test Case 5 Failed");


/**
 * 原创解法：
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses2 = function(s) {
    let stack=[];
    let res=[];
    const bracket={')':'('}
    for(let i=s.length;i>=0;i--){
        const element=s[i]
        if(bracket[element]){
            stack.push(element)
        }else{
           const ele= stack.pop()
           console.log(stack)
            if(ele!=undefined){
                if(!res[stack.length]){
                    res[stack.length]=''
                }
                res[stack.length]+='()'
            }
            
        }
    }
    console.log(res,stack)
    let max=0;
    res.forEach(val=>{
        console.log(val)
        if(val)max=Math.max(max,val.length)
        
    })
    return max
};

console.log(longestValidParentheses("(())"))